/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package optimizacion.problemas;

import ec.util.MersenneTwisterFast;
import java.io.IOException;

/**
 *
 * @author USUARIO
 */
public class DosOpt {

    public static double[][] nodos;
    public static void main(String[] args) {
        String ruta = "src\\optimizacion\\resources\\berlin52.tsp";
        int numeroNodos = 52;
        TSPFileReader lector = new TSPFileReader(0, new double[numeroNodos][2], ruta);

        try {
            MersenneTwisterFast prng = new MersenneTwisterFast(321654987);
            int n = 10000;
            lector.readFile();
            nodos = lector.getCoordinates();
            int[] solucion = new int[52];
            int[] solucionOptima = new int[52];
            double distanciaOptima = Double.MAX_VALUE;
            double distancia;
            int nodo;
            for (int i = 0; i < n; i++) {
//                System.out.println("--------------------------------------------");
                distancia = 0;
                nodo = (int) Math.floor(prng.nextDouble() * 52);
                solucion[0] = nodo;
//                System.out.println(1 + " : " + solucion[0]);
                for (int j = 1; j < numeroNodos; j++) {
                    boolean esta;
                    do {
                        esta = false;
                        nodo = (int) Math.floor(prng.nextDouble() * 52);
                        for (int k = 0; k < j; k++) {
                            if (nodo == solucion[k]) {
                                esta = true;
                                break;
                            }
                        }
                    } while (esta);
                    solucion[j] = nodo;
//                    System.out.println((j+1) + " : " + solucion[j]);
                    distancia += Math.sqrt((nodos[nodo][0] - nodos[solucion[j - 1]][0]) * (nodos[nodo][0] - nodos[solucion[j - 1]][0])
                            + (nodos[nodo][1] - nodos[solucion[j - 1]][1]) * (nodos[nodo][1] - nodos[solucion[j - 1]][1]));
                }
                if (distancia < distanciaOptima) {
                    distanciaOptima = distancia;
                    System.arraycopy(solucion, 0, solucionOptima, 0, solucion.length);
                }
            }
            Nodo lista = new Nodo(nodos[solucionOptima[0]][0], nodos[solucionOptima[0]][1], solucionOptima[0], null,null);
            Nodo next = lista;
            Nodo nodoX = null;
            for (int i = 1; i < solucionOptima.length; i++) {
                int j = solucionOptima[i];
                nodoX = new Nodo(nodos[j][0], nodos[j][1], j, null, null);
                next.setNextNodo(nodoX);
                nodoX.setBeforeNodo(next);
                next = nodoX;
            }
            nodoX.setNextNodo(lista);
            lista.setBeforeNodo(nodoX);
            System.out.println();
            distanciaOptima = calcularDistancia(lista);
            System.out.println("distancia optima: " + distanciaOptima);
            double distanciaActual;
            double distanciaNueva;
            Nodo a1n2 = null;
            Nodo a1n1 = lista.getBeforeNodo();
            for (int i = 0; i < solucionOptima.length - 2; i++) {
                a1n1 = a1n1.getNextNodo();
                a1n2 = a1n1.getNextNodo();
                Nodo a2n2 = a1n2.getNextNodo();
                Nodo a2n1 = null;
                for (int j = i+2; j < solucionOptima.length - 1; j++) {
                    a2n1 = a2n2;
                    a2n2 = a2n1.getNextNodo();
                    distanciaActual = Math.sqrt(Math.pow(nodos[a1n1.getPosicion()][0] - nodos[a1n2.getPosicion()][0], 2) + Math.pow(nodos[a1n1.getPosicion()][1] - nodos[a1n2.getPosicion()][1], 2)) + 
                                      Math.sqrt(Math.pow(nodos[a2n1.getPosicion()][0] - nodos[a2n2.getPosicion()][0], 2) + Math.pow(nodos[a2n1.getPosicion()][1] - nodos[a2n2.getPosicion()][1], 2));
                    distanciaNueva = Math.sqrt(Math.pow(nodos[a1n1.getPosicion()][0] - nodos[a2n1.getPosicion()][0], 2) + Math.pow(nodos[a1n1.getPosicion()][1] - nodos[a2n1.getPosicion()][1], 2)) + 
                                     Math.sqrt(Math.pow(nodos[a1n2.getPosicion()][0] - nodos[a2n2.getPosicion()][0], 2) + Math.pow(nodos[a1n2.getPosicion()][1] - nodos[a2n2.getPosicion()][1], 2));
                    if (distanciaActual > distanciaNueva) {
                        System.out.println("\n----------------------------------------------------------------------------------------------------------");
                        System.out.println("cruce entre: " + a1n1.getPosicion() + " " + a2n2.getPosicion());
                        System.out.println("\ndistancia nueva: " + (distanciaOptima - distanciaActual + distanciaNueva));
                        cruzar(a1n1,a2n2);
                        System.out.println("\ndistancia lista:" + calcularDistancia(lista));
                        distanciaOptima += distanciaNueva - distanciaActual;
                    }
                    
                }
            }
            
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    private static void cruzar(Nodo a1n1, Nodo a2n2) {
        Nodo nuevoFinal = a1n1.getNextNodo();
        Nodo nuevoComienzo = a2n2.getBeforeNodo();
        a1n1.setNextNodo(nuevoComienzo);
        a2n2.setBeforeNodo(nuevoFinal);
        Nodo nextNodo = nuevoFinal;
        //System.out.println("\n----------------------------------------------------------------------------------------------------------");
        //System.out.println("\n cambios: ");
        while (true) {
            if (nextNodo.getPosicion() == nuevoComienzo.getPosicion()) {
                break;
            }
            Nodo nextNodo1 = nextNodo.getNextNodo();
            nextNodo.setNextNodo(nextNodo.getBeforeNodo());
            nextNodo.setBeforeNodo(nextNodo1);
            //System.out.println(nextNodo.getBeforeNodo().getPosicion() + " " + nextNodo.getPosicion() + " " + nextNodo.getNextNodo().getPosicion());
            nextNodo = nextNodo1;
        }
        System.out.println();
        //nuevoFinal.setBeforeNodo(nuevoFinal.getNextNodo());
        nuevoFinal.setNextNodo(a2n2);
        nuevoComienzo.setNextNodo(nuevoComienzo.getBeforeNodo());
        nuevoComienzo.setBeforeNodo(a1n1);
    }

    private static double calcularDistancia(Nodo lista) {
        double distancia = 0;
        Nodo next = lista;
        for (int i = 0; i < 51; i++) {
            System.out.print(next.getPosicion() + " ");
            distancia += Math.sqrt(Math.pow(nodos[next.getPosicion()][0] - nodos[next.getNextNodo().getPosicion()][0], 2) + Math.pow(nodos[next.getPosicion()][1] - nodos[next.getNextNodo().getPosicion()][1], 2));
            next = next.getNextNodo();
        }
        System.out.print(next.getPosicion());
        System.out.println();
        return distancia;
    }
}
